import java.util.ArrayList;
import java.util.Random;

/**
 * Date: 2019/2/23
 * Time: 15:07
 * User: Driss.
 *
 * 冒泡排序和插入排序的性能对比：
 * 随机生成 10000 个数组，每个数组中包含 200 个数据，然后在我的机器上分别用冒泡和插入排序算法来排序，统计各自花费时间
 */
public class TestBublleSortAndInsertionSort {

    private static int ARR_COUNT = 10000;
    private static int NUMBERS = 200;

    /**
     * 随机产生ARR_COUNT个数组，每个数组包含NUMBERS个数据
     * @return
     */
    public static ArrayList<int[]> generateArray(){
        Random random = new Random(NUMBERS);

        ArrayList<int[]> ints = new ArrayList<int[]>(ARR_COUNT);
        for (int j = 0; j < ARR_COUNT; j++) {
            int[] arr = new int[NUMBERS];
            for (int i = 0; i < NUMBERS; i++) {
                arr[i] =  random.nextInt(NUMBERS);
            }

            ints.add(arr);
        }
        return ints;
    }


    /**
     * 冒泡排序：不断比较相邻两个元素的大小
     * 未优化的冒泡排序需要的排序次数等于数组的大小
     * @param a 数组
     */
    public static void bublleSort(int[] a){
        if(a.length <=1 )
            return;

        //外层for循环决定需要冒泡排序的次数
        for (int i = 0; i <a.length ; i++) {
            for (int j = 0; j < a.length - 1; j++) {
                if(a[j] > a[j+1]){ //交换
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
    }


    /**
     * 优化后的冒泡排序：当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。
     * @param a
     */
    public static void optimizationBublleSort(int[] a){
        if(a.length <=1 )
            return;

        //外层for循环决定需要冒泡排序的次数
        for (int i = 0; i <a.length ; i++) {

            //提前退出冒泡循环的标志位
            boolean flag = false;
            for (int j = 0; j < a.length - 1; j++) {
                if(a[j] > a[j+1]){ //交换
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;

                    //表示有数据交换
                    flag = true;
                }
            }

            if(!flag)
                break;  //没有数据交换，提前退出
        }
    }

    /**
     * 插入排序
     * 核心思想：将数组中的数据分为两个区间，已排序区间和未排序区间，取未排序区间中的元素，在已排序区间中找到合适的位置将其插入，并保证已排序区间数据一直有序
     */
    public static void insertionSort(int[] a){
        if(a.length <= 1)
            return;

        for (int i = 1; i < a.length; i++) {
            int temp = a[i];
            int j = i;
            for (; j > 0 ; j--) {
                if(temp < a[j-1])
                    a[j] = a[j-1];  //数据移动
                else
                    break;
            }
            a[j] = temp;
        }
    }

    /**
     * 选择排序：每次从未排序区间找到最小元素，放到已排序区间
     * @param a
     */
    public static void selectionSort(int[] a){

        //遍历无序区间，第一次选择排序的无序区间是整个数组
        for (int i = 0; i < a.length; i++) {
            //先找到最小的元素以及其下标
            int minElement = a[i];
            int index = i;
            for(int j = i+1; j < a.length;j++){
                if(a[j] < minElement) {
                    minElement = a[j];
                    index = j;
                }
            }

            //交换元素，将最小元素放置无需区间的第一个位置上
            a[index] = a[i];
            a[i] = minElement;
        }
    }

    //打印数组
    public static String printArray(int[] a){
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < a.length; i++) {
            stringBuilder.append(a[i]);
            stringBuilder.append(" ");
        }
        return stringBuilder.toString();
    }


    public static void testSort(){
        int[] a = {33,4,5,3,2,12,14,11,10,6,5};
        selectionSort(a);
        System.out.println(printArray(a));
    }


    public static void main(String[] args) {

        testSort();

//        ArrayList<int[]> ints = generateArray();
//        long begin1 = System.currentTimeMillis();
//        for (int i = 0; i < ARR_COUNT; i++) {
//            int[] arr = ints.get(i);
//            optimizationBublleSort(arr);
//        }
//        long end1 = System.currentTimeMillis();
//        System.out.println("使用优化后的冒泡排序需要时间" +  Long.toString(end1  - begin1) + "ms");
//
//        long begin2 = System.currentTimeMillis();
//        for (int i = 0; i < ARR_COUNT; i++) {
//            int[] arr = ints.get(i);
//            insertionSort(arr);
//        }
//        long end2 = System.currentTimeMillis();
//        System.out.println("使用优化后的插入排序需要时间" +  Long.toString(end2  - begin2) + "ms");

    }

}
